// 138.随机链表的复制
package LeetcodeHot100;

import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Solution138 {
    public Node copyRandomList(Node head) {
        Node result = head; // 保存副本
        // 保存原始结点和副本结点
        Map<Node, Node> map = new HashMap<>();
        // 遍历一次结点，新建副本结点
        while (head != null) {
            map.put(head, new Node(head.val));
            head = head.next;
        }
        // 对于每个结点，设置副本结点的指针
        for (Node node : map.keySet()) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
        }
        // 返回结果
        return map.get(result);
    }
}
